335. Игра с переключателями

Имеется бесконечное количество лампочек, находящихся в выключенном состоянии. На каждом этапе игры включаются (если они были выключены) или выключаются (если они были включены) все те лампочки, номера которых кратны номеру этапа игры.

Определить состояние n-той лампочки после n-го этапа игры.

Вход. Сначала задано количество тестов t (1 ≤ t ≤ 10). Далее следует t строк с указанием номера n (0 < n ≤ 10⁵) этапа игры.

Выход. Вывести t строк с указанием состояния соответствующей лампочки: 0 – лампочка выключена, 1 – включена.

Пример входа	Пример выхода
2 1 5	1 0

РЕШЕНИЕ

математика

Анализ алгоритма

Пятая лампочка поменяет свое состояние на первой и пятой фазе игры (так как 5 делится только на 1 и 5). Поскольку изначально она была выключена, то после пятой фазы она также будет выключенной. Если n имеет четное число делителей, то после n -ой фазы она снова будет выключенной. И наоборот, если n имеет нечетное количество делителей, то после n -ой фазы она будет включенной. Случай нечетного количества делителей возможен только если n является полным квадратом. Если число является полным квадратом, то все его простые делители входят в его разложение на простые множители с четными степенями. Если n = , то его число делителей равно d(n) = (a₁ + 1) * (a₂ + 1) * … * (a_k + 1). Если n – полный квадрат, то все a_i четны. А значение d(n) нечетно, так как является произведением нечетных чисел.

Реализация алгоритма

Читаем входные данные. Если значение n является полным квадратом, то выводим 1. Иначе выводим 0.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

r = (int)sqrt(n);

printf("%d\n",r*r == n);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int r = (int)Math.sqrt(1.0*n);

System.out.println(r*r == n ? 1 : 0);

}

}

}

Python реализация

import math

tests = int(input())

while (tests > 0):

tests -= 1

n = int(input())

sqr = math.sqrt(n)

if (sqr == int(sqr)):

print(1)

else :

print(0)